import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2025-10-28
 * Time: 11:22
 */
class Solution{
    public int findKthLargest(int[] nums, int k){
        return qsort(nums, 0, nums.length-1, k);
    }

    public int qsort(int[] nums, int l, int r, int k){
        if(l == r) return nums[l];

        //1.定义一个基准
        int key = nums[new Random().nextInt(r - l +1)];

        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(nums[i] < key) swap(nums, ++left, i++);
            else if(nums[i] > key) swap(nums, --right, i);
            else i++;
        }

        int b = right - left - 1, c = r - right + 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

    public void swap(int[] nums, int n, int m){
        int t = nums[n];
        nums[n] = nums[m];
        nums[m] = t;
    }
}


public class demo2 {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3,4,5,6,7};
        System.out.println(s.findKthLargest(nums, 2));
    }
}
